package com.practice.stack;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Stack;

/**
 * Evaluate math expression, supports (), +, -, *, / (A)
 */
public class EvaluateExpression {
	private HashMap<String, Integer>	m_precedence;
	
	public EvaluateExpression() {
		m_precedence = new HashMap<String, Integer>();
		m_precedence.put("+", 1);
		m_precedence.put("-", 1);
		m_precedence.put("*", 2);
		m_precedence.put("/", 2);
	}
	
	public int eval(String expr) {
		ArrayList<String> postfix = buildPostfix(expr);
		Stack<Integer> stack = new Stack<Integer>();
		
		for (String s : postfix) {
			if (s.matches("\\d*")) {
				stack.push(Integer.parseInt(s));
			}
			else {
				int b = stack.pop();
				int a = stack.pop();
				if ("+".equals(s)) {
					stack.push(a + b);
				}
				else if ("-".equals(s)) {
					stack.push(a - b);
				}
				else if ("*".equals(s)) {
					stack.push(a * b);
				}
				else if ("/".equals(s)) {
					stack.push(a / b);
				}
			}
		}
		
		return stack.pop();
	}
	
	private ArrayList<String> buildPostfix(String expr) {
		ArrayList<String> result = new ArrayList<String>();
		char[] c = expr.toCharArray();
		Stack<String> stack = new Stack<String>();
		
		for (int i=0; i<c.length; i++) {
			if (c[i] == ' ') continue;
			if (c[i] >= '0' && c[i] <= '9') {
				StringBuilder token = new StringBuilder();
				while (i<c.length && c[i]>='0' && c[i]<='9') {
					token.append(c[i]);
					i++;
				}
				result.add(token.toString());
				i--;
				continue;
			}
			
			String ch = c[i] + "";
			if (m_precedence.containsKey(ch)) {
				while (!stack.isEmpty()) {
					String top = stack.peek();
					if (top.equals("(") || m_precedence.get(top) < m_precedence.get(ch)) break;
					result.add(stack.pop());
				}
				stack.push(ch);
			}
			else if (ch.equals("(")) {
				stack.push(ch);
			}
			else {		// ch.equals(")")
				while (!stack.isEmpty()) {
					String top = stack.peek();
					if (top.equals("(")) {
						stack.pop();
						break;
					}
					result.add(stack.pop());
				}
			}
		}
		
		while (!stack.isEmpty()) {
			result.add(stack.pop());
		}
		
		return result;
	}
}
